# amount = 5
# coins = [1, 2, 5]
# amount = 3
# coins = [2]
amount = 10
coins = [10]
def change(amount,coins):
    #创建dp状态转移矩阵
    dp=[[0 for _ in range(amount+1)] for _ in range(len(coins))]
    #先处理第一行状态
    for i in range(amount+1):
        if int(i)%int(coins[0])==0:
            dp[0][i]=1
    for i in range(1,len(coins)):
        for j in range(amount+1):
            if j<coins[i]:
                dp[i][j]=dp[i-1][j]
            elif j==coins[i]:
                dp[i][j]=dp[i-1][j]+1
            else:
                #j>coins[i]
                dp[i][j]=dp[i-1][j]+dp[i][j-coins[i]]
    return dp[len(coins)-1][amount]
print(change(amount,coins))
